/*
 * Copyright 2014 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#ifndef SkPathOpsTSect_DEFINED
#define SkPathOpsTSect_DEFINED

#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkArenaAlloc.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsRect.h"
#include "src/pathops/SkPathOpsTCurve.h"
#include "src/pathops/SkPathOpsTypes.h"

#include <cstdint>

class SkIntersections;
class SkTSect;
class SkTSpan;
struct SkDLine;

#ifdef SK_DEBUG
typedef uint8_t SkOpDebugBool;
#else
typedef bool SkOpDebugBool;
#endif

static inline bool SkDoubleIsNaN(double x)
{
    return x != x;
}

class SkTCoincident {
public:
    SkTCoincident()
    {
        this->init();
    }

    void debugInit()
    {
#ifdef SK_DEBUG
        this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN;
        this->fPerpT = SK_ScalarNaN;
        this->fMatch = 0xFF;
#endif
    }

    char dumpIsCoincidentStr() const;
    void dump() const;

    bool isMatch() const
    {
        SkASSERT(!!fMatch == fMatch);
        return SkToBool(fMatch);
    }

    void init()
    {
        fPerpT = -1;
        fMatch = false;
        fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
    }

    void markCoincident()
    {
        if (!fMatch) {
            fPerpT = -1;
        }
        fMatch = true;
    }

    const SkDPoint &perpPt() const
    {
        return fPerpPt;
    }

    double perpT() const
    {
        return fPerpT;
    }

    void setPerp(const SkTCurve &c1, double t, const SkDPoint &cPt, const SkTCurve &);

private:
    SkDPoint fPerpPt;
    double fPerpT; // perpendicular intersection on opposite curve
    SkOpDebugBool fMatch;
};

struct SkTSpanBounded {
    SkTSpan *fBounded;
    SkTSpanBounded *fNext;
};

class SkTSpan {
public:
    SkTSpan(const SkTCurve &curve, SkArenaAlloc &heap)
    {
        fPart = curve.make(heap);
    }

    void addBounded(SkTSpan *, SkArenaAlloc *);
    double closestBoundedT(const SkDPoint &pt) const;
    bool contains(double t) const;

    void debugInit(const SkTCurve &curve, SkArenaAlloc &heap)
    {
#ifdef SK_DEBUG
        SkTCurve *fake = curve.make(heap);
        fake->debugInit();
        init(*fake);
        initBounds(*fake);
        fCoinStart.init();
        fCoinEnd.init();
#endif
    }

    const SkTSect *debugOpp() const;

#ifdef SK_DEBUG
    void debugSetGlobalState(SkOpGlobalState *state)
    {
        fDebugGlobalState = state;
    }

    const SkTSpan *debugSpan(int) const;
    const SkTSpan *debugT(double t) const;
    bool debugIsBefore(const SkTSpan *span) const;
#endif
    void dump() const;
    void dumpAll() const;
    void dumpBounded(int id) const;
    void dumpBounds() const;
    void dumpCoin() const;

    double endT() const
    {
        return fEndT;
    }

    SkTSpan *findOppSpan(const SkTSpan *opp) const;

    SkTSpan *findOppT(double t) const
    {
        SkTSpan *result = oppT(t);
        SkOPASSERT(result);
        return result;
    }

    SkDEBUGCODE(SkOpGlobalState *globalState() const { return fDebugGlobalState; })

        bool hasOppT(double t) const
    {
        return SkToBool(oppT(t));
    }

    int hullsIntersect(SkTSpan *span, bool *start, bool *oppStart);
    void init(const SkTCurve &);
    bool initBounds(const SkTCurve &);

    bool isBounded() const
    {
        return fBounded != nullptr;
    }

    bool linearsIntersect(SkTSpan *span);
    double linearT(const SkDPoint &) const;

    void markCoincident()
    {
        fCoinStart.markCoincident();
        fCoinEnd.markCoincident();
    }

    const SkTSpan *next() const
    {
        return fNext;
    }

    bool onlyEndPointsInCommon(const SkTSpan *opp, bool *start, bool *oppStart, bool *ptsInCommon);

    const SkTCurve &part() const
    {
        return *fPart;
    }

    int pointCount() const
    {
        return fPart->pointCount();
    }

    const SkDPoint &pointFirst() const
    {
        return (*fPart)[0];
    }

    const SkDPoint &pointLast() const
    {
        return (*fPart)[fPart->pointLast()];
    }

    bool removeAllBounded();
    bool removeBounded(const SkTSpan *opp);

    void reset()
    {
        fBounded = nullptr;
    }

    void resetBounds(const SkTCurve &curve)
    {
        fIsLinear = fIsLine = false;
        initBounds(curve);
    }

    bool split(SkTSpan *work, SkArenaAlloc *heap)
    {
        return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap);
    }

    bool splitAt(SkTSpan *work, double t, SkArenaAlloc *heap);

    double startT() const
    {
        return fStartT;
    }

private:
    // implementation is for testing only
    int debugID() const
    {
        return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
    }

    void dumpID() const;

    int hullCheck(const SkTSpan *opp, bool *start, bool *oppStart);
    int linearIntersects(const SkTCurve &) const;
    SkTSpan *oppT(double t) const;

    void validate() const;
    void validateBounded() const;
    void validatePerpT(double oppT) const;
    void validatePerpPt(double t, const SkDPoint &) const;

    SkTCurve *fPart;
    SkTCoincident fCoinStart;
    SkTCoincident fCoinEnd;
    SkTSpanBounded *fBounded;
    SkTSpan *fPrev;
    SkTSpan *fNext;
    SkDRect fBounds;
    double fStartT;
    double fEndT;
    double fBoundsMax;
    SkOpDebugBool fCollapsed;
    SkOpDebugBool fHasPerp;
    SkOpDebugBool fIsLinear;
    SkOpDebugBool fIsLine;
    SkOpDebugBool fDeleted;
    SkDEBUGCODE(SkOpGlobalState *fDebugGlobalState);
    SkDEBUGCODE(SkTSect *fDebugSect);
    PATH_OPS_DEBUG_T_SECT_CODE(int fID);
    friend class SkTSect;
};

class SkTSect {
public:
    SkTSect(const SkTCurve &c SkDEBUGPARAMS(SkOpGlobalState *) PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
    static void BinarySearch(SkTSect *sect1, SkTSect *sect2, SkIntersections *intersections);

    SkDEBUGCODE(SkOpGlobalState *globalState() { return fDebugGlobalState; }) bool hasBounded(const SkTSpan *) const;

    const SkTSect *debugOpp() const
    {
        return SkDEBUGRELEASE(fOppSect, nullptr);
    }

#ifdef SK_DEBUG
    const SkTSpan *debugSpan(int id) const;
    const SkTSpan *debugT(double t) const;
#endif
    void dump() const;
    void dumpBoth(SkTSect *) const;
    void dumpBounded(int id) const;
    void dumpBounds() const;
    void dumpCoin() const;
    void dumpCoinCurves() const;
    void dumpCurves() const;

private:
    enum { kZeroS1Set = 1, kOneS1Set = 2, kZeroS2Set = 4, kOneS2Set = 8 };

    SkTSpan *addFollowing(SkTSpan *prior);
    void addForPerp(SkTSpan *span, double t);
    SkTSpan *addOne();

    SkTSpan *addSplitAt(SkTSpan *span, double t)
    {
        SkTSpan *result = this->addOne();
        SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
        result->splitAt(span, t, &fHeap);
        result->initBounds(fCurve);
        span->initBounds(fCurve);
        return result;
    }

    bool binarySearchCoin(SkTSect *, double tStart, double tStep, double *t, double *oppT, SkTSpan **oppFirst);
    SkTSpan *boundsMax();
    bool coincidentCheck(SkTSect *sect2);
    void coincidentForce(SkTSect *sect2, double start1s, double start1e);
    bool coincidentHasT(double t);
    int collapsed() const;
    void computePerpendiculars(SkTSect *sect2, SkTSpan *first, SkTSpan *last);
    int countConsecutiveSpans(SkTSpan *first, SkTSpan **last) const;

    int debugID() const
    {
        return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
    }

    bool deleteEmptySpans();
    void dumpCommon(const SkTSpan *) const;
    void dumpCommonCurves(const SkTSpan *) const;
    static int EndsEqual(const SkTSect *sect1, const SkTSect *sect2, SkIntersections *);
    bool extractCoincident(SkTSect *sect2, SkTSpan *first, SkTSpan *last, SkTSpan **result);
    SkTSpan *findCoincidentRun(SkTSpan *first, SkTSpan **lastPtr);
    int intersects(SkTSpan *span, SkTSect *opp, SkTSpan *oppSpan, int *oppResult);
    bool isParallel(const SkDLine &thisLine, const SkTSect *opp) const;
    int linesIntersect(SkTSpan *span, SkTSect *opp, SkTSpan *oppSpan, SkIntersections *);
    bool markSpanGone(SkTSpan *span);
    bool matchedDirection(double t, const SkTSect *sect2, double t2) const;
    void matchedDirCheck(double t, const SkTSect *sect2, double t2, bool *calcMatched, bool *oppMatched) const;
    void mergeCoincidence(SkTSect *sect2);

    const SkDPoint &pointLast() const
    {
        return fCurve[fCurve.pointLast()];
    }

    SkTSpan *prev(SkTSpan *) const;
    bool removeByPerpendicular(SkTSect *opp);
    void recoverCollapsed();
    bool removeCoincident(SkTSpan *span, bool isBetween);
    void removeAllBut(const SkTSpan *keep, SkTSpan *span, SkTSect *opp);
    bool removeSpan(SkTSpan *span);
    void removeSpanRange(SkTSpan *first, SkTSpan *last);
    bool removeSpans(SkTSpan *span, SkTSect *opp);
    void removedEndCheck(SkTSpan *span);

    void resetRemovedEnds()
    {
        fRemovedStartT = fRemovedEndT = false;
    }

    SkTSpan *spanAtT(double t, SkTSpan **priorSpan);
    SkTSpan *tail();
    bool trim(SkTSpan *span, SkTSect *opp);
    bool unlinkSpan(SkTSpan *span);
    bool updateBounded(SkTSpan *first, SkTSpan *last, SkTSpan *oppFirst);
    void validate() const;
    void validateBounded() const;

    const SkTCurve &fCurve;
    SkSTArenaAlloc<1024> fHeap;
    SkTSpan *fHead;
    SkTSpan *fCoincident;
    SkTSpan *fDeleted;
    int fActiveCount;
    bool fRemovedStartT;
    bool fRemovedEndT;
    bool fHung;
    SkDEBUGCODE(SkOpGlobalState *fDebugGlobalState);
    SkDEBUGCODE(SkTSect *fOppSect);
    PATH_OPS_DEBUG_T_SECT_CODE(int fID);
    PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount);
#if DEBUG_T_SECT
    int fDebugAllocatedCount;
#endif
    friend class SkTSpan;
};

#endif
